#pragma once
using namespace std;

// Definition for a Node.
//class Node {
//public:
//    int val;
//    Node* next;
//    Node* random;
//
//    Node(int _val) {
//        val = _val;
//        next = NULL;
//        random = NULL;
//    }
//};
//
//
//class Solution {
//public:
//    Node* copyRandomList(Node* head)
//    {
//        if (head == nullptr)
//            return nullptr;
//
//        map<Node*, Node*> copyMap;
//        Node* newHead = nullptr, * newTail = nullptr;
//        Node* cur = head;
//        while (cur)
//        {
//            Node* newNode = new Node(cur->val);
//            if (newHead == nullptr)
//            {
//                newHead = newTail = newNode;
//            }
//            else
//            {
//                newTail->next = newNode;
//                newTail = newTail->next;
//            }
//            //copyMap[cur] = cur->random;
//            copyMap[cur] = newNode;
//            cur = cur->next;
//        }
//
//        cur = head;
//        Node* newCur = newHead;
//        while (cur)
//        {
//            if (cur->random == nullptr)
//            {
//                newCur->random = nullptr;
//            }
//            else
//            {
//                //newCur->random = new Node(copyMap[cur]->val);
//                newCur->random = copyMap[cur->random];
//            }
//            newCur = newCur->next;
//            cur = cur->next;
//        }
//        return newHead;
//
//    }
//};


//class Solution {
//
//    struct Compare
//    {
//        bool operator()(const pair<string, int>& left, const pair<string, int>& right) const
//        {
//            if (left.second > right.second)
//                return true;
//            else
//                return false;
//
//        }
//    };
//
//public:
//    vector<string> topKFrequent(vector<string>& words, int k)
//    {
//        map<string, int> m;
//        for (auto key : words)
//        {
//            m[key] += 1;
//        }
//
//        vector<pair<string, int>> tmp(m.begin(), m.end());
//        stable_sort(tmp.begin(), tmp.end(), Compare());
//
//        vector<string> ret;
//        for (auto au : tmp)
//        {
//            if (k > 0)
//            {
//                ret.push_back(au.first);
//                k--;
//            }
//            else
//            {
//                break;
//            }
//        }
//        return ret;
//    }
//};